#ifndef BVH_PROFILE_BUILD_H
#define BVH_PROFILE_BUILD_H
#include "BVH.h"

using namespace GxLibBasic;

namespace RayTracePro
{
#ifdef PROFILE_BVH
	template <typename T, typename TEval>
	void BuildBvhFromSubTrees(Bvh_Build<T> & bvh, Array<BuildData<BvhNode_Build<T> *>, true> & elements, TEval eval)
	{
Int64 Profile_BadSplits = 0;
		struct BvhJob
		{
			BvhNode_Build<T> ** result;
			BuildData<BvhNode_Build<T> *>* elements;
			IntPtr elementCount;
			BvhJob()
			{}
			BvhJob(BvhNode_Build<T> ** result, BuildData<BvhNode_Build<T> *>* elements, IntPtr elementCount)
			{
				this->elements = elements;
				this->elementCount = elementCount;
				this->result = result;
			}
		};
		const int stackSize = 256;
		BvhJob stack[stackSize];
		int stackPtr = 0;
		auto pushJob = [&](BvhNode_Build<T> ** result, BuildData<BvhNode_Build<T> *>* elements, IntPtr elementCount)
		{
			BvhJob job(result, elements, elementCount);
			if (stackPtr < stackSize)
				stack[stackPtr++] = job;
			else
				throw "stack overflow";
		};
		auto popJob = [&]()->BvhJob
		{
			if (stackPtr)
				return stack[--stackPtr];
			else
				throw "stack empty";
		};

		BvhNode_Build<T> * rs = 0;
		BvhJob job(&rs, elements.Buffer(), elements.Count());
		while (true)
		{
			BvhNode_Build<T> * node = new BvhNode_Build<T>();
			//nodeCount++;
			(*job.result) = node;
			BuildData<BvhNode_Build<T> *>* elements = job.elements;
			IntPtr elementCount = job.elementCount;
			if (elementCount == 0)
			{
				printf("elementCount = 0 !");
				throw 0;
			}
			if (elementCount == 1 || stackPtr == stackSize)
			{
				delete node;
				(*job.result) = (*elements[0].Element);
				if (!stackPtr)
					break;
				else
					job = popJob();
				continue;
			}
			else
			{
				BBox centroidBounds;
				BBox bbox;
				centroidBounds.Init();
				bbox.Init();
				for (int i = 0; i < elementCount; i++)
				{
					centroidBounds.Union(elements[i].Center);
					bbox.Union(elements[i].Bounds);
				}
				node->Bounds = bbox;
				int dim = centroidBounds.MaxDimension();
				BucketInfo buckets[nBuckets];
				for (int i = 0; i<elementCount; i++)
				{
					int b = (int)(nBuckets *
						((elements[i].Center[dim] - centroidBounds.Min[dim]) / (centroidBounds.Max[dim] - centroidBounds.Min[dim])));
					if (b == nBuckets) b = nBuckets-1;
					Assert(b >= 0 && b < nBuckets);
					buckets[b].count+=(*elements[i].Element)->ElementCount;
					buckets[b].bounds.Union(elements[i].Bounds);
				}

				float cost[nBuckets-1];
				for (int i = 0; i < nBuckets-1; i++)
				{
					BBox b0, b1;
					b0.Init();
					b1.Init();
					int count0 = 0, count1 = 0;
					for (int j = 0; j <= i; j++)
					{
						b0.Union(buckets[j].bounds);
						count0 += buckets[j].count;
					}
					for (int j = i+1; j < nBuckets; j++)
					{
						b1.Union(buckets[j].bounds);
						count1 += buckets[j].count;
					}

					cost[i] = eval.EvalCost(count0, SurfaceArea(b0), count1, SurfaceArea(b1), SurfaceArea(bbox));
				}
 
				float minCost = cost[0];
				int minCostSplit = 0;
				for (int i = 1; i < nBuckets-1; i++)
				{
					if (cost[i] < minCost)
					{
						minCost = cost[i];
						minCostSplit = i;
					}
				}

				if (elementCount > 1)
				{
					BuildData<BvhNode_Build<T> *>*pmid = std::partition(elements,
						elements + elementCount,
						[&](const BuildData<BvhNode_Build<T> *> &p)
						{
							int b = (int)(nBuckets * ((p.Center[dim] - centroidBounds.Min[dim]) /
								 (centroidBounds.Max[dim] - centroidBounds.Min[dim])));
							if (b == nBuckets) b = nBuckets-1;
							Assert(b >= 0 && b < nBuckets);
							return b <= minCostSplit;
						});
					node->Axis = dim;
	#ifdef PROFILE_BVH
					if (minCostSplit == 0)
					{
						float endCost = eval.EvalCost(0, (bbox.Max[(dim+1)%3]-bbox.Min[(dim+1)%3])*(bbox.Max[(dim+2)%3]-bbox.Min[(dim+2)%3]), (int)elementCount, SurfaceArea(bbox), SurfaceArea(bbox));
						if (endCost < minCost)
						{
							int valAdd = 1;//1<<(32-depth);
							bvh.Profile_Lock.Lock();
							bvh.Profile_BadSplits += valAdd;
							bvh.Profile_Lock.Unlock();
							node->IsBadNode = true;
						}
					}
					if (pmid == elements)
						pmid = elements + 1;
					else if (pmid == elements + elementCount)
						pmid = elements + elementCount-1;
	#endif
					job = BvhJob(node->Children, elements, pmid-elements);
					pushJob(node->Children+1, pmid, elements + elementCount - pmid);
				}
				else
				{
					delete node;
					(*job.result) = *(elements[0].Element);
					if (!stackPtr)
						break;
					else
						job = popJob();
					continue;
				}
			}
		}
		bvh.Root = rs;
	}


#endif
}

#endif